-- This is the (naive) Sieve of Eratosthenes. Public domain.

local bit = require("bit")
local band, bxor, rshift, rol = bit.band, bit.bxor, bit.rshift, bit.rol

local function nsieve(p, m)
    local count = 0
    for i = 0, rshift(m, 5) do
        p[i] = -1
    end
    for i = 2, m do
        if band(rshift(p[rshift(i, 5)], i), 1) ~= 0 then
            count = count + 1
            for j = i + i, m, i do
                local jx = rshift(j, 5)
                p[jx] = band(p[jx], rol(-2, j))
            end
        end
    end
    return count
end

if arg and arg[1] then
    local N = tonumber(arg[1]) or 1
    if N < 2 then
        N = 2
    end
    local primes = {}

    for i = 0, 2 do
        local m = (2 ^ (N - i)) * 10000
        io.write(string.format("Primes up to %8d %8d\n", m, nsieve(primes, m)))
    end
else
    assert(nsieve({}, 10000) == 1229)
end
